#include <bits/stdc++.h>

using namespace std;

// 含有嵌套的字符串解码
// 测试链接 : https://leetcode.cn/problems/decode-string/

class Solution 
{
private:
    int where;

    string get(int cnt, const string& str)
    {
        string ans;
        for(int i = 0; i < cnt; ++i) ans += str;
        return ans;
    }

	// s[i....]开始计算，遇到字符串终止 或者 遇到 ] 停止
	// 返回 : 自己负责的这一段字符串的结果
	// 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    string f(string& s, int i)
    {
        int cnt = 0;
        string path;
        while(i < s.size() && s[i] != ']')
        {
            if(s[i] >= '0' && s[i] <= '9')
                cnt = 10 * cnt + s[i++] - '0';
            else if(s[i] != '[') // 字母
                path += s[i++];
            else
            {
                // 遇到 [ 
				// cnt = 7 * ? 
                path.append(get(cnt, f(s, i + 1)));
                i = where + 1;
                cnt = 0;
            }
        }
        where = i;
        return path;
    }

public:
    string decodeString(string s) 
    {
        where = 0;
        return f(s, 0);
    }
};


class Solution 
{
public:
    string decodeString(string s) 
    {
        stack<int> st1;
        stack<string> st2;
        st2.push("");
        int i = 0, n = s.size();
        while(i < n)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int x = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                {
                    x = 10 * x + s[i++] - '0';
                }
                st1.push(x);
            }
            else if(s[i] == '[')
            {
                string str;
                ++i;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    str += s[i++];
                }
                st2.push(str);
            }
            else if(s[i] == ']')
            {
                string tmp = st2.top();
                st2.pop();
                int k = st1.top();
                st1.pop();
                while(k--)
                {
                    st2.top() += tmp;
                }
                ++i;
            }
            else
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st2.top() += tmp;
            }
        }

        return st2.top();
    }
};